//class Solution {
//public:
//    int m, n, aim;
//    bool vis[310][310] = { 0 };
//    bool searchMatrix(vector<vector<int>>& matrix, int target) {
//        m = matrix.size(), n = matrix[0].size();
//        aim = target;
//        return dfs(matrix, 0, 0);
//    }
//
//    bool dfs(vector<vector<int>>& matrix, int i, int j)
//    {
//        vis[i][j] = true;
//        if (matrix[i][j] == aim) return true;
//        if (matrix[i][j] > aim) return false;
//
//        std::cout << matrix[i][j] << " ";
//        bool ans1 = false, ans2 = false;
//        if (i + 1 < m && !vis[i + 1][j])
//            ans1 = dfs(matrix, i + 1, j);
//        if (j + 1 < n && !vis[i][j + 1])
//            ans2 = dfs(matrix, i, j + 1);
//        return ans1 || ans2;
//    }
//};


//class Solution {
//public:
//    bool searchMatrix(vector<vector<int>>& matrix, int target) {
//        int m = matrix.size(), n = matrix[0].size();
//        int i = 0, j = n - 1;
//        while (i < m && j >= 0)
//        {
//            if (matrix[i][j] > target) j--;
//            else if (matrix[i][j] < target) i++;
//            else return true;
//        }
//        return false;
//    }
//};



